#include <iostream>
#include <set>
#include <string>

using namespace std;

std::set<std::string> generateBalancedParenthesis(int numberOfPair)
{
	std::set<std::string> previousStepResult;
	if ( numberOfPair < 1)
		return previousStepResult;
	previousStepResult.insert("()");
	for(int i = 1; i < numberOfPair;++i)
	{
		std::set<std::string> currentStepResult;
		std::set<std::string>::iterator itr = previousStepResult.begin();
		for(;itr != previousStepResult.end();++itr)
		{
			currentStepResult.insert("(" + *itr + ")");
			currentStepResult.insert("()" + *itr);
			currentStepResult.insert(*itr + "()");
		}
		previousStepResult = currentStepResult;
	}
	return previousStepResult;
}

void printBalancedParenthesis(string currentCombination, unsigned int remainedLeftBraces, unsigned int remainedRightBraces)
{
	if (0 == remainedRightBraces )
	{
		cout<<currentCombination<<endl;
		return;
	}
	if (remainedLeftBraces > 0)
	{
		printBalancedParenthesis(currentCombination + "(" , remainedLeftBraces -1, remainedRightBraces);
		if (remainedRightBraces > remainedLeftBraces )
		{
			printBalancedParenthesis(currentCombination + ")" , remainedLeftBraces , remainedRightBraces-1);
		}
	}
	else
	{
		printBalancedParenthesis(currentCombination + ")" , remainedLeftBraces, remainedRightBraces-1);
	}
}

int main()
{
	/*std::set<string> balancedParenthesis = generateBalancedParenthesis(1);
	std::set<string>::iterator  itr= balancedParenthesis.begin();
	for(;itr!=balancedParenthesis.end();itr++)
	{
		cout<<*itr<<endl;
	}*/

	printBalancedParenthesis("",4,4);
	return 0;
}